//
// Created by liushuai on 2021/1/27.
//

#include "mergeKLists.h"
ListNode *mergeList(ListNode* head1,ListNode* head2) {
    if(head1&&!head2)
        return head1;
    else if(!head1&&head2)
        return head2;
    else if(!head1&&!head2)
        return head1;
    else{
        if(head1->val<head2->val) {
            head1->next = mergeList(head1->next, head2);
            return head1;
        }
        else{
            head2->next = mergeList(head1,head2->next);
            return head2;
        }
    }
}
ListNode *mergeKLists(vector<ListNode *> &lists){
    if(lists.empty())
        return nullptr;
    else if(lists.size()==1)
        return lists[0];
    else{
        ListNode* res= nullptr;
        do {
            res = mergeList(lists[0],lists[1]);
            lists.erase(lists.begin(),lists.begin()+2);
            lists.push_back(res);
        }while (lists.size()!=1);
        return lists[0];

    }
}